// ; 广度优化搜索（Breadth-First Optimization Search，BFO）是一种在搜索算法中优化路径搜索的方法，它结合了广度优先搜索（Breadth-First Search，BFS）和优化算法的思想。BFO 旨在找到一条从起点到终点的最短路径，同时考虑到路径的成本或权重。

// ; 基本原理
// ; 广度优先搜索：BFS 是一种遍历树或图的算法，它从一个节点开始，逐层遍历节点，即先访问起始节点的所有邻接节点，再访问邻接节点的邻接节点，依此类推。
// ; 优化：在广度优先搜索的基础上，BFO 会考虑路径的权重，以找到最短的路径。这通常涉及到为每个节点分配一个估计成本，该成本是基于从起点到当前节点的已知最短路径的权重。

// ; 工作流程
// ; 初始化：从起点开始，将起点加入到一个队列中，并为起点分配一个成本（通常是0）。
// ; 层级遍历：从队列中取出一个节点，检查其所有未访问的邻接节点。
// ; 成本计算：为每个邻接节点计算成本，这通常是从起点到该邻接节点的路径的累积权重。
// ; 节点更新：如果通过当前节点到达邻接节点的成本比之前计算的成本更低，则更新该邻接节点的成本，并将其加入到队列中。
// ; 继续搜索：重复步骤2-4，直到队列为空或找到目标节点。
// ; 路径重建：一旦找到目标节点，可以通过回溯每个节点的最优前驱节点来重建最短路径。

class Queue {
  constructor() {
    this.items = [];
  }

  enqueue(item) {
    this.items.push(item);
  }

  dequeue() {
    if (this.isEmpty()) return null;
    return this.items.shift();
  }

  isEmpty() {
    return this.items.length === 0;
  }

  front() {
    if (this.isEmpty()) return null;
    return this.items[0];
  }
}

function breadthFirstSearch(graph, start, end) {
  const queue = new Queue();
  const visited = new Set();
  const paths = new Map(); // 存储从起点到每个节点的最短路径

  // 初始化起点的最短路径
  paths.set(start, { path: [start], weight: 0 });

  queue.enqueue({ node: start, weight: 0 });

  while (!queue.isEmpty()) {
    const current = queue.dequeue();

    const currentPath = paths.get(current.node).path;
    const currentWeight = paths.get(current.node).weight;

    console.log('====current node====', current);
    console.log('====queue====', queue);
    console.log('====paths====', paths);

    if (current.node === end) {
      return currentPath; // 找到终点，返回最短路径
    }

    if (!visited.has(current.node)) {
      visited.add(current.node);

      graph.getNeighbors(current.node).forEach(neighbor => {
        if (!visited.has(neighbor)) {
          // 计算通过当前节点到邻居节点的边的权重
          const edgeWeight = 1; // 假设每条边的权重为1

          // 更新邻居节点的最短路径
          const newWeight = currentWeight + edgeWeight;
          const newPath = currentPath.concat(neighbor);

          if (!paths.has(neighbor) || newWeight < paths.get(neighbor).weight) {
            paths.set(neighbor, { path: newPath, weight: newWeight });

            queue.enqueue({ node: neighbor, weight: newWeight });
          }
        }
      });
    }
  }

  return null; // 如果没有找到终点，则返回 null
}

// 示例图，使用邻接列表表示
const graph = {
  'A': ['B', 'C'],
  'B': ['A', 'D', 'E'], 
  'C': ['A', 'F'],
  'D': ['B'],
  'E': ['B', 'F'],
  'F': ['C', 'E']
};

// 定义获取邻居节点的函数
graph.getNeighbors = function(node) {
  return this[node] || [];
};

// 执行 BFS 搜索
const startNode = 'A';
const endNode = 'F';
const shortestPath = breadthFirstSearch(graph, startNode, endNode);

console.log(shortestPath); // 输出: ['A', 'C', 'F']

module.exports = Queue